a) Field of the Invention
The invention is directed to a process for the electronic recording of an image of the surface of an object, which image can be displayed as a function G(x, y), wherein x and y are the coordinates of a respective image point of the image and G designates its gray value, wherein the object is recorded sequentially over different times ti, where ti+1 greater than ti, from different perspectives as function Gi in order to form the total image G from the individual images Gi(x, y) such as when rolling a finger for recording a fingerprint, wherein portions are cut out of the individual images and joined together depending on the respective recorded view. The invention is further directed to an apparatus with a device for the electronic recording of an image of the surface of an object, which image can be displayed as image points by a function G(x, y), wherein x and y are the coordinates of the respective image point with an assigned gray value G, and with a device by which the object is imaged sequentially over different times ti where ti+1 greater than ti, from different perspectives as function Gi in order to form the total image Gi from the individual images Gi(x, y) such as when rolling a finger for the recording of a fingerprint, and an electronic image processing device whose circuit is designed to cut portions out of the individual images and join them together depending on the respective recorded view. The invention is further directed to a use of the process in an arrangement of the type described above.
b) Description of the Related Art
While image acquisition of flat images is presently carried out in a standard manner, there has been an increasing interest within technical circles in the imaging of three-dimensional bodies. Examples of applications in this respect include the recording of three-dimensional bodies in three spatial dimensions or two surface dimensions. These applications include tomography in the field of medicine and, in the consumer branch, automatic acquisition of human body dimensions for computer-assisted manufacture of tailor-cut clothing.
With techniques of these types, It is known to image a body from a plurality of views, wherein, in particular, an image recording device is guided around the body. In so doing, a plurality of recordings are made and the three-dimensional image of the body or the two-dimensional developed view of the surface is then reconstructed from these recordings in a computer.
The recording of the surface of a finger for acquiring fingerprints in criminology or for future applications for personal identification in security systems is more difficult.
The identification of persons has recently become a focus of interest in a computer technology. In the last year, for example, COMPAQ has offered computers which determine a numerical code from a fingerprint which can be used instead of a password for access to the Internet or for identification when making purchases on the Internet. For this purpose, the lines of the finger are determined by placing the finger on a sensor.
Compared with the examples mentioned above, the recording of fingerprints is particularly problematic. Because of the elasticity of the finger, the relevant lines of the finger can be displaced in the different recordings of the fingerprints, so that unique association is rendered dubious without special steps for classification.
For this reason, but also because of legal restrictions in most countries, it is attempted in criminology to record fingerprints in such a way that the technique of inking the finger to be recorded and rolling it on paper is simulated as far as possible. In so doing, a glass plate is usually used instead of paper, light being radiated onto the glass plate under total reflection conditions. When the finger is rolled, the lines of the finger interfere with total reflection due to their contact with the glass plate, so that the points of support are dark, resulting in a situation optically similar to that of a finger rolled on paper. The image occurring with different light intensities due to the total reflection is then electronically recorded and evaluated.
Although the process and apparatus which will be shown in more detail in the following can also be used for other applications such as those mentioned above by way of example, the following constructions are essentially directed to fingerprinting technique because the resulting set of problems in acquiring a curved surface can be shown especially clearly in this case.
During the rolling for electronic recording of individual images, recordings are made at determined times, so that the total image exists in steps as partial images of the rolling process, whereas a continuous imaging is carried out when recording on paper. The stepwise recording leads to the problem of deciding how to assemble the images. A simple assembly of the individual images is generally impossible because the finger deforms when rolled and even the structure of the lines of the finger changes when rolling. Similar problems also occur in tomography when the patient moves. Further, this is also true in the case of manufacturing tailored clothing by means of computers when the customer does not keep still. But this set of problems is particularly pronounced in the recording of fingerprints.
Known methods for reconstructing a total surface from individual images are known from U.S. Pat. No. 4,933,976, U.S. Pat. No. 5,230,025 and WO 97/41528. According to the teachings of these patents, a strip is removed the individual images and the total image is assembled from these strips. The cited patents differ from one another with respect to the different algorithms by which the strip boundary is determined in order, as far as possible, to join only parts of the individual images that correspond to the supporting surface of the finger. However, distorted or corrupted images can only be taken into account to a limited extent in the computing methods indicated in this case.
Inspection of the images recorded by these different methods show that many finger lines do not fit together perfectly or the image looks blurred with overlapping strips whose image content is averaged, which may be attributed to a slipping process of the finger at right angles to the rolling direction.
Conceivably, the matching of partial images could be improved by known mathematical algorithms for displacements, stretching and rotations, but the computing expenditure for mathematical processes of this type is so high that, given present processor speeds, the computing time for matching the large number of images recorded during the rolling process makes it impossible to record and evaluate the images within a time period comparable to that for rolling. In computing processes of this type, it would be more practical to roll a finger on paper in the standard way and to electronically process the flat fingerprint image made on the paper.
For these reasons, it is necessary and an object of the invention to assemble sequentially acquired individual images electronically to form a total image in such a way that falsification due to unwanted movements of the imaged object can be taken into account better than is possible when strip-shaped partial images are fitted together, wherein the method used should also be capable of optimization with respect to shorter computing times compared to the image recording times.
Based on the process mentioned above, this object is met in that a curved intersection line is determined for defining the portions of every image aside from the first image by comparison with the image content of the previously recorded or assembled image Gixe2x88x921, wherein the portion of the image Gixe2x88x921 is defined by this curved intersection line and the corresponding portion of the image Gi is subsequently added to this intersection line to form the total image G (x, y), wherein this intersection line is determined by forming a similarity function Gc(x, y) between the images Gi and Gixe2x88x921, which similarity function Gc(x, y) is external with identical gray values at identical image point coordinates or also by including their surroundings, and the intersection line is formed by a curve y (x) which runs through at least one extreme with a very high similarity of the similarity function Gc(x, y).
Accordingly, proceeding from the apparatus mentioned above, an apparatus is characterized in that the circuit of the image processing device is designed for determining a curved intersection line in order to determine the portions of every image aside from the first image Gi by comparison with the image content of the previously recorded and assembled image Gixe2x88x921, for defining or limiting the portion of the image Gixe2x88x921 through this intersection line and subsequently adding to this intersection line the corresponding portion of the image Gi to form the total image G(x, y), and in that a processor is provided in the circuit which determines this intersection line by forming a similarity function Gc(x, y) between the images Gi and Gixe2x88x921 which is external with identical gray values at identical image point coordinates or also by including their surroundings, and the intersection line is formed by a curve y(x) which, as far as possible, runs through an extreme of very high similarity of the similarity function Gc(x, y).
In contrast to the prior art, a curved intersection line is used for this purpose. A curved intersection line is substantially more suitable for simulating actual conditions because the supporting surface of the finger also has no straight-line boundaries.
Having established this characteristic, model calculations could have been applied for suitable intersection lines instead of the straight-line boundary of the strips according to the prior art in view of the required low computing speed. However, this course is not taken in the present case. On the contrary, the intersection line is obtained by means of a similarity function.
Similarity functions are well known in mathematics. In this case, four different functions are indicated, for example, wherein the alphabetic character s refers to one function and the alphabetic character e refers to another function between which the similarity is described mathematically. The angled brackets around the variables s and e designate an averaging over a predetermined surrounding of an image point by means of which the summing indicated by the addition symbols is also carried out. The functions e and s depend on the coordinates x and y even when this is not expressly noted.
1. Cross-correlation function:       r    xy    =            ∑                        (                                    e              i                        -                          ⟨              e              ⟩                                )                ·                  (                                    s              i                        -                          ⟨              s              ⟩                                )                                              ∑          i                ⁢                  xe2x80x83                ⁢                                            (                                                e                  i                                -                                  ⟨                  e                  ⟩                                            )                        2                    ⁢                      ∑                                          (                                                      s                    i                                    -                                      ⟨                    s                    ⟩                                                  )                            2                                          
2. Sum of square differences:       d    xy    =            ∑      i              xe2x80x83              ⁢          xe2x80x83        ⁢                  (                              s            i                    -                      e            i                          )            2      
3. Sum of difference function:       d    xy    =            ∑      i              xe2x80x83              ⁢          "LeftBracketingBar"              xe2x80x83            ⁢                        s          i                -                  e          i                    "RightBracketingBar"      
4. Sum of differences without averaging:       d    xy    =            ∑      i              xe2x80x83              ⁢          "LeftBracketingBar"              xe2x80x83            ⁢                        s          i                -                  e          i                -                  ⟨          s          ⟩                +                  ⟨          e          ⟩                    "RightBracketingBar"      
In the cross-correlation function, the denominator is the mean square deviation from the average which is compared with the actual deviation at every point by dividing by the term in the numerator. In areas in which there is no structure, the denominator is a measure of the noise which is accordingly compared with the noise at every image point. In these areas, the cross-correlation function has a value in the order of magnitude of 1. The value can be even higher when the deviation in the numerator is substantially higher than the noise because of different structures in the images represented by e and s. When there are strikingly identical structures, the individual value is equal to the average value, specifically with both functions s and e, so that the cross-correlation function approaches the value zero at which the similarity is accordingly the highest possible.
However, because of the root and the quotients above all, this cross-correlation function is computation-intensive. On the other hand, the second similarity function is processed more quickly because it directly compares the two functions s and e. In the case of a large deviation in the structures, the function value d is very large, which can be attributed, among other reasons, to the square. When the structures correspond, the value of d approaches zero. The value of d is limited to a minimum of zero because of the squaring.
The third similarity function indicated has a form similar to that described above. It contains a sum over the absolute value of difference functions of functions s and e and thus behaves similar to the preceding similarity function. However, it is processed more quickly since no squares need to be formed. Of course, due to the absence of squares, this function does not increase as steeply as the preceding function in cases of dissimilarity. But this is irrelevant in the present instance because the invention is geared toward maximum similarity and the computation accordingly moves essentially in the minimum of the similarity functions.
The last function indicated compares the deviations of average values of functions s and e. In this way, a constant component in the surroundings being considered is compensated and the variations in the structure are more pronounced in the similarity function. In the absence of similarity, this function accordingly also increases more sharply than the preceding function. However, since the process according to the invention is directed to maximum similarity, (s) is approximately (e) in the areas of concern for evaluation of fingerprints, so that no large deviations are expected in relation to the preceding function as a result.
The preceding discussion shows that the selection of the similarity function itself is essentially not at all the issue. Any function which delivers an external value with identical structures and which assumes a value deviating from the extreme in the case of deviations between the structures is suitable for the process according to the invention.
Because of the large number of possible functions, a function by which the computing time can be optimized can also always be found under very different boundary conditions. Therefore, the optimizing possibility required in the stated object of the invention is also achieved according to the invention.
Only a few external points could be referred to for determining the intersection line in order to keep the computing time low. For example, a polynomial could be made through the selected extreme points for determining the intersection line, wherein, for example, the extreme points are selected at the upper image boundary, the lower image boundary and the middle and the polygon is a parabola.
Improved results which unexpectedly work faster than a polynomial approximation by using suitable algorithms is provided according to a preferred further development of the invention in that an intersection line is determined for the curve y(x), wherein the sum of the values of the similarity function Gc(x, y(x) along the curve y(x) is external with respect to similarity.
The improvement in matching partial images can possibly be attributed to the fact that the entire curve is determined through an individual extreme obtained by addition instead of only by several extreme values at individual points as in the polynomial approximation that was mentioned by way of example.
The increased computing speed can possibly be explained in that only addition is carried out in this case instead of the polynomial approximation for an intersection line mentioned above by way of example which would require the matching of n coefficients with formation of powers of n for a polynomial of the nth degree.
According to an advantageous further development, the computing and storing time are reduced in particular in that the similarity function is minimal in the case of similarity of the image contents of the images to be compared, in that a minimum for the intersection line is obtained by the Bellman method in which the curve yj(xi) characterized by image points j is selected in each instance for that value yj with the associated xi for which a sum S(x, y) is minimal over the entire region, which sum S(x, y) is given recursively from the previous sum values S(xjxe2x88x921, yj):
S(xj, yj)=Gc(xj, yi), the starting value k=1, and for k greater than 1: S(xk, yj)=Gc(xk, yi)+min {S(xkxe2x88x921, yv): ixe2x88x921xe2x89xa6Vxe2x89xa6i+1}.
This process is illustrated in more detail in the following with reference to an embodiment example.
According to the process according to the invention, similarity functions could be obtained from the two individual images for determining the intersection lines of two partial images. However, this could cause uncertainty when the intersection line of two individual images intersects the intersection line of the preceding two sectional images, which is certainly possible because a finger will deform when rolled. These difficulties are avoided in a preferred further development of the invention in that, for time ti an instantaneous total image GM is put together from all of the preceding partial images Gk (k less than i), and in that the similarity function is formed with this instantaneous total image GM by comparison with the partial image Gi recorded at time ti.
The process characterized according to the further development is particularly suitable for optimizing a real-time calculation with minimal storage because not all of the individual images need to be buffered up to the end of the rolling process, after which they are assembled. In this case, only the instantaneous partial image GM is continued, wherein this instantaneous partial image GM represents the desired total image of the surface already after the conclusion of the rolling process and after the last recorded partial image has been taken into account computationally.
As was already made clear, certain similarity functions are especially suitable for computer processing. According to a preferred further development of the invention, these similarity function include those in which the similarity function is a function proportional to the absolute value of the difference itself or the difference of the deviation from the average of the gray values, this function being averaged over the surroundings of Nxc3x97M image points, wherein the extreme to be found is a minimum. Such functions include, for example, the above-mentioned functions rxy and dxy.
In particular, it is provided according to an advantageous further development of the process that a similarity function Gc describing the similarity of two functions F1 and F2 is formed by             G      C        ⁡          (                        x          i                ,                  y          k                    )        =            ∑              v        =                              -            N                    /          2                            N        /        2              ⁢          xe2x80x83        ⁢                  ∑                  μ          =                                    -              M                        /            2                                    M          /          2                    ⁢              xe2x80x83            ⁢              "LeftBracketingBar"                  [                      xe2x80x83                    ⁢                      "AutoLeftMatch"                                          "AutoLeftMatch"                                                                            F                      1                                        ⁡                                          (                                                                        x                                                      i                            +                            v                                                                          ,                                                  y                                                      k                            +                            μ                                                                                              )                                                        -                                                            m                      1                                        ⁡                                          (                                                                        x                          i                                                ,                                                  y                          k                                                                    )                                                                      ]                            -                              [                                  xe2x80x83                                ⁢                                                      "AutoLeftMatch"                                                                                            F                          2                                                ⁡                                                  (                                                                                    x                                                              i                                +                                v                                                                                      ,                                                          y                                                              k                                +                                μ                                                                                                              )                                                                    -                                              xe2x80x83                                            ⁢                                                                        m                          2                                                ⁡                                                  (                                                                                    x                              i                                                        ,                                                          y                              k                                                                                )                                                                                      ]                                    ,                                                                        
wherein                     m                  1          ,          2                    ⁡              (                              x            i                    ,                      y            k                          )              =                  1                              (                          N              +              1                        )                    ·                      (                          M              +              1                        )                              ⁢                        ∑                      v            =                                          -                N                            /              2                                            N            /            2                          ⁢                  xe2x80x83                ⁢                              ∑                          μ              =                                                -                  N                                /                2                                                    N              /              2                                ⁢                      xe2x80x83                    ⁢                                                    F                                  1                  ,                  2                                            ⁡                              (                                                      x                                          i                      +                      v                                                        ,                                      y                                          k                      +                      μ                                                                      )                                      ⁢                          xe2x80x83                        ⁢            or            ⁢                          xe2x80x83                        ⁢            is            ⁢                          xe2x80x83                        ⁢            zero                                ,
and for every nth time tn, in particular F1=Gn and F2 equals Gnxe2x88x921 or the gray value function of a total image assembled from all preceding partial images Gm(m less than n).
These statements about the similarity function correspond to the above nomenclature of the sum of the difference function and the sum of the differences without averaging. As was already mentioned, the latter are especially advantageous for minimizing computing time
The summing over the surroundings of Nxc3x97M image points is carried out in order to balance local structure values such as are given, for example, with the finger lines of the fingertip for determining the optical path. Further, noise participation is reduced by summing.
In individual images with little noise, the computing time can be further reduced. The balancing with respect to minimal structures is achieved not only when the step size of 1 is maintained, as usual, in summing, that is, when all neighboring image points take part in the summing, but, rather, when a larger step size is selected, that is, for example, only every second, fourth and sixth image point is used for summing over the surroundings. Therefore, according to a preferred further development of the invention, in order to reduce the computing time, the step size is greater than a distance between image points in at least one summing.
As was already discussed in detail, it is especially advantageous when smaller structures contribute only a little to the similarity function. Therefore, the structure is xe2x80x9cblurredxe2x80x9d or balanced by means of summing over Nxc3x97M image points. Accordingly, it is provided in a preferred further development of the invention that a value greater than one width and, in particular, more than two widths of the minimum structures occurring in the images is selected for N and M, wherein the minimum structure in fingerprint acquisition is the average distance between neighboring finger lines.
Taking into account two widths of the minimal structures in the finger images means an optimal blurring of the structures with minimal computing time as can be illustrated by means of the known sampling theorem. However, providing only one width of the minimum structures occurring in the images has likewise proven suitable in practice and is optimal, above all, in case of reduced structure blurring, in order to keep the computing time short.
As will be appreciated by the person skilled in the art, the computing time essentially depends on the quantity of image points to be accounted for in the image comparison. In order to drastically reduce the number of image points for the subsequent computing process, the calculation of a mask marking the area of the finger that is visible simultaneously in both images is provided. For this purpose, both images are initially put in binary form and the surrounding contour of the black image points is determined. The logical AND operation carried out with the contoured zones of two images supplies the above-mentioned mask which masks the image areas in which subsequent similarity functions and the intersection curve are determined.
While calculation of a mask represents additional computing time, it has turned out that the computing time is drastically reduced by the reduction in the number of image points in subsequent steps, whereas the additional computing expenditure brought about by AND and OR operations in particular is negligible.
Further, the computing time can be greatly reduced when the quantity of images is reduced. However, the number of image points when rolling a finger for recording fingerprints, which is mentioned by way of example, can vary widely depending on how quickly the finger is rolled. In order to limit the quantity of images to a reasonable amount, it is provided according to an advantageous further development of the invention that a central point is determined for every recorded image and an image with a central point distance from the preceding image stored as Gi which is less than a predetermined comparison distance is rejected, that is, is not stored as Gi+1 and is not taken into account in forming the total image.
It has turned out to be sufficient, particularly in fingerprinting techniques, when a maximum of fifty images are recorded, so that, according to another development of the process according to the invention, it is provided that the comparison distance given beforehand is selected in such a way that a maximum of 50 images are recorded when using the process in the prescribed manner.
The further developments described above involved central point calculations; however, these can be very time-consuming depending on the required computing accuracy. In order to reduce computing time, it is suggested according to an advantageous further development of the invention that a line central point is calculated already during the image readout for every line and the average of the line central points over all lines is used subsequently as a central point for the respective image.
As has already been made clear from the preceding description, this process is especially suitable for the recording of fingerprints by rolling. Consequently, an application of the process is also provided according to the invention in the above-mentioned apparatus for electronic image recording and image processing of fingerprints.